package org.example.game.history;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/14 16:51
 */

//给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为
//c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。
//
// 你可以从 任一 单元格开始，并且必须至少移动一次。
//
// 返回你能得到的 最大 总得分。
//
//
//
// 示例 1：
//
//
// 输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
//
//
// 输出：9
//
// 解释：从单元格 (0, 1) 开始，
// 并执行以下移动：
// - 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。
// - 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。 总得分为 2 + 7 = 9 。
//
// 示例 2：
//
//
//
//
// 输入：grid = [[4,3,2],[3,2,1]]
//
//
// 输出：-1
//
// 解释：从单元格 (0, 0) 开始，执行一次移动：从 (0, 0) 到 (0, 1) 。得分为 3 - 4 = -1 。
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 2 <= m, n <= 1000
// 4 <= m * n <= 10⁵
// 1 <= grid[i][j] <= 10⁵
//
//
// 👍 3 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

public class Solution3148 {

    public static void main(String[] args) {

        Solution3148 solution = new Solution3148();
        List<List<Integer>> grid = new ArrayList<>();

        grid.add(Arrays.asList(4,3,2));
        grid.add(Arrays.asList(3,2,1));


        System.out.println(solution.maxScore(grid));
    }

    public int maxScore(List<List<Integer>> grid) {

        //1. 标记矩阵内最小值
        int m = grid.size();
        int n = grid.get(0).size();

        int[][] arr = new int[m][n];
        int[][] minArr = new int[m][n];
        int x = 0;
        int y = 0;
        for(List<Integer> list : grid){
            for(Integer val : list){
                arr[x][y] = val;
                y++;
            }
            x++;
            y = 0;
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i == 0 && j==0){
                    minArr[i][j] = arr[i][j];
                }else if(i == 0){
                    minArr[i][j] = Math.min(arr[i][j], minArr[i][j-1]);
                }else if(j == 0){
                    minArr[i][j] = Math.min(arr[i][j], minArr[i-1][j]);
                }else {
                    minArr[i][j] = Math.min(arr[i][j], Math.min(minArr[i][j-1], minArr[i-1][j]));
                }
            }
        }
        //2. 计算grid[i][j] - 最小值
        int max = Integer.MIN_VALUE;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) {
                if(i == 0 && j==0){
                    max = Integer.MIN_VALUE;
                }else if(i == 0){
                    max = Math.max(max, arr[i][j] - minArr[i][j-1]);
                }else if(j == 0){
                    max = Math.max(max, arr[i][j] - minArr[i-1][j]);
                }else {
                    max = Math.max(max, Math.max(arr[i][j] - minArr[i-1][j], arr[i][j] - minArr[i][j-1]));
                }

            }
        }
        return max;
    }
}
